
import java.util.Arrays;

class Solution {
    /**
     * 统计数组中任意三个数可以构成三角形的个数
     * @param nums
     */
    public int triangleNumber(int[] nums) {
        //1.排序
        Arrays.sort(nums);
        //2.统计
       int ret = 0,len = nums.length;
        for(int i =  len - 1;i >= 2;i--){
            int left = 0,right = i -1;
            while(left < right){
                //两边之和小于第三边
                if(nums[left] + nums[right] <= nums[i]){
                    left++;
                    //两边之和大于第三边
                }else{
                    ret += (right - left);
                    right--;
                }
            }
        }
        return ret;
    }

    public static void main(String[] args) {
        Solution main  = new Solution();
        main.triangleNumber(new int[]{2,2,3,4});
    }
}

class Solution1 {
    //二分查找

    /**
     * 时间复杂度：O（logN）
     * 空间复杂度：O（1）
     * @param price
     * @param target
     * @return
     */
    public int searchIndex(int[] price,int target){
        int left = 0,right = price.length - 1;

        while(left < right){
            int mid = left + (right - left) /2;
            if(price[mid] > target){
                right = mid -1;
            }else if(price[mid] < target){
                left = mid + 1;
            }else{
                return mid;
            }
        }
        return left;
    }
    public int[] twoSum(int[] price, int target) {
        int index = searchIndex(price,target - price[0]);

        for(int i = index;i >= 1;i--){
            int find = searchIndex(price,target - price[i]);
            if(price[find] + price[i] == target){
                return new int[]{price[find],price[index]};
            }
        }
        return null;
    }

    public static void main(String[] args) {
        Solution1 test = new Solution1();
        test.twoSum(new int[]{8, 21, 27, 34, 52, 66},61);
    }
}